package com.mlh.dp.old;
// 你打算构建一些障碍赛跑路线。给你一个 下标从 0 开始 的整数数组 obstacles ，数组长度为 n ，其中 obstacles[i] 表示第 i 个障碍的高度。
// 对于每个介于 0 和 n - 1 之间（包含 0 和 n - 1）的下标  i ，在满足下述条件的前提下，请你找出 obstacles 能构成的最长障碍路线的长度：
// 你可以选择下标介于 0 到 i 之间（包含 0 和 i）的任意个障碍。
// 在这条路线中，必须包含第 i 个障碍。
// 你必须按障碍在 obstacles 中的 出现顺序 布置这些障碍。
// 除第一个障碍外，路线中每个障碍的高度都必须和前一个障碍 相同 或者 更高 。
// 返回长度为 n 的答案数组 ans ，其中 ans[i] 是上面所述的下标 i 对应的最长障碍赛跑路线的长度。

// 输入：obstacles = [1,2,3,2]
// 输出：[1,2,3,3]
// 解释：每个位置的最长有效障碍路线是：
// - i = 0: [1], [1] 长度为 1
// - i = 1: [1,2], [1,2] 长度为 2
// - i = 2: [1,2,3], [1,2,3] 长度为 3
// - i = 3: [1,2,3,2], [1,2,2] 长度为 3

//读题思考：这为什么是困难题目  这就是递增子序列啊  但不是严格的  他甚至都把dp数组的含义告诉你了

public class LongestObstacleCourseAtEachPosition {

    //dp 时间复杂度达到n的2次方  超出时间限制
    public int[] method1(int[] obstacles){
        int[]ans=new int[obstacles.length];
        ans[0]=1;
        for(int i=1;i<ans.length;i++){
            for(int j=i-1;j>=0;j--){
                if(obstacles[i]>=obstacles[j]){
                    ans[i]=Math.max(ans[i],ans[j]);
                }
            }
            ans[i]++;
        }
        return ans;
    }

    //利用二分查找
    public int[] method2(int[] obstacles){
        int n=obstacles.length;
        int[]ans=new int[n];
        int[]res=new int[n];
        res[0]=obstacles[0];
        ans[0]=1;
        int len=0;
        for(int i=1;i<n;i++){
             if(obstacles[i]>=res[len]){
                 res[++len]=obstacles[i];
                 ans[i]=len+1;
             }else{
                 int l=0,r=len,pos=0;
                 while(l<=r){
                     int mid=l+r>>1;
                     if(res[mid]>obstacles[i]){ //这边改成大于的话 就变成找到第一个大于obstacles[i]的数  此时就可以替换他
                         //为什么之前的递增子序列不能用大于呢
                         //因为如果那边找到第一个大于他的数  他的前一个数有两种可能
                         // (1)小于nums[i] (2)等于nums[i]
                         //如果是等于的话替换掉第一个大于的数字  会参数错误 因为此时就不符合严格递增了
                         pos=mid;
                         r=mid-1;
                     }else{
                         l=mid+1;
                     }
                 }
                 res[pos]=obstacles[i];
                 ans[i]=pos+1;
             }
        }
        return ans;
    }

}
